function BinarySearchTree() {

  // 封装内部节点类
  function Node(key) {
    this.key = key
    this.left = null
    this.right = null
  }

  this.root = null

  // 1.插入操作
  BinarySearchTree.prototype.insert = function(key) {
    let newNode = new Node(key)

    // 二叉搜素树为空
    if (this.root === null) {
      this.root = newNode
      return this
    }

    this.insertNode(this.root, newNode)
    return this
  }

  // 插入操作的递归
  BinarySearchTree.prototype.insertNode = function(node, newNode) {
    if (newNode.key < node.key) {
      if (node.left === null) return node.left = newNode
      this.insertNode(node.left, newNode)
    } else {
      if (node.right === null) return node.right = newNode
      this.insertNode(node.right, newNode)
    }
  }

  // 2. 二叉搜索树的遍历
  // >1.先序遍历
  BinarySearchTree.prototype.preOrderTranversal = function(handler) {
    this.preOrderTranversalNode(this.root, handler)
  }

  // 先序遍历递归操作
  BinarySearchTree.prototype.preOrderTranversalNode = function(node, handler) {
    if (node != null) {
      handler(node.key)

      // 递归遍历左节点
      this.preOrderTranversalNode(node.left, handler)

      // 递归遍历右节点
      this.preOrderTranversalNode(node.right, handler)
    }
  }

  // >2.中序遍历
  BinarySearchTree.prototype.midOrderTranversal = function(handler) {
    this.midOrderTranversalNode(this.root, handler)
  }

  // 中序遍历递归操作
  BinarySearchTree.prototype.midOrderTranversalNode = function(node, handler) {
    if (node != null) {
      // 递归遍历左节点
      this.midOrderTranversalNode(node.left, handler)
      handler(node.key)

      // 递归遍历右节点
      this.midOrderTranversalNode(node.right, handler)
    }
  }

  // >3.后序遍历
  BinarySearchTree.prototype.backOrderTranversal = function(handler) {
    this.backOrderTranversalNode(this.root, handler)
  }

  //后序遍历递归
  BinarySearchTree.prototype.backOrderTranversalNode = function(node, handler) {
    if (node != null) {
      // 递归遍历左节点
      this.backOrderTranversalNode(node.left, handler)

      // 递归遍历右节点
      this.backOrderTranversalNode(node.right, handler)

      handler(node.key)
    }
  }

  //3.获取最值
  // >1.最大值
  BinarySearchTree.prototype.min = function() {
    let crt = this.root
    while (crt.left) crt = crt.left
    return crt.key
  }

  // >2.最小值
  BinarySearchTree.prototype.max = function() {
    let crt = this.root
    while (crt.left) crt = crt.right
    return crt.key
  }

  // 4.搜素方法
  BinarySearchTree.prototype.search = function(key) {
    let crt = this.root
    while (crt != null) {
      if (key < crt.key) crt = crt.left
      else if (key > crt.key) crt = crt.right
      else return true
    }
    return false
  }

  // 5.删除操作
  BinarySearchTree.prototype.remove = function(key) {
    /**
     * 需要三个变量，被删除的节点，被删除节点的父节点，一个变量用于记录父节点的被删除的节点方向
     * 分为三种情况
     * （1）被删除的是叶节点
     * > 被删除的是根节点，没有父节点（全二叉树只有一个节点）
     * > 被删除的是普通叶节点，有父节点
     * （2）被删除的节点只有一个子节点
     * > 被删除的是根节点，没有父节点
     * > 被删除的是普通节点，有父节点
     * （3）被删除的节点有两个子节点
     * > 被删除的是根节点
     * > 被删除的是普通节点
     */

    // 先判断节点是否存在
    if (!this.search(key)) return null

    let fNode = null // 父节点
    let cNode = this.root // 记录当前节点（用于查找被删除的节点）
    let isLefted = true // 记录当前节点是父节点的哪一侧

    while (cNode.key != key) {
      fNode = cNode
      if (key < cNode.key) {
        isLefted = true
        cNode = cNode.left
      } else {
        isLefted = false
        cNode = cNode.right
      }
    }

    // 找到了被删除的节点
    if (cNode.left === null && cNode.right === null) {
      // 1.叶节点
      if (!fNode) {
        // 叶节点为根节点
        this.root = null
        return true
      }
      isLefted ? fNode.left = null : fNode.right = null
      return true
    } else if ((cNode.left === null && cNode.right) || (cNode.right === null && cNode.left)) {
      // 2.只有一个子节点
      if (!fNode) {
        // 该节点为根节点
        this.root = cNode.left ? cNode.left : cNode.right
        return true
      }
      if (cNode.left) {
        isLefted ? fNode.left = cNode.left : fNode.right = cNode.left
      } else {
        isLefted ? fNode.left = cNode.right : fNode.right = cNode.right
      }
      return true
    } else {
      // 3.有两个子节点

      /**
       * > 寻找前驱或后继（需要记录前驱的父节点，前驱节点）
       * > 把前驱替换到被删除节点的位置
       */

      // 前驱的父节点，前驱节点
      let [fPrecursor, precursor] = this.getPrecursor(cNode.right)
      if (!fNode) {
        // 删除节点为根节点
        this.root = precursor
        fPrecursor.left = precursor.right
        precursor.left = cNode.left
        precursor.right = cNode.right
        return true
      }

      // 删除节点为正常节点
      precursor.left = cNode.left
      fPrecursor.left = precursor.right
      precursor.right = cNode.right
      isLefted ? fNode.left = precursor : fNode.right = precursor
      return true
    }
  }

  BinarySearchTree.prototype.getPrecursor = function(node) {
    let fNode = node // 前驱的父节点
    let cNode = fNode.left // 记录当前节点，用于找到前驱
    while (cNode.left) {
      fNode = cNode
      cNode = cNode.left
    }
    return [fNode, cNode]
  }

}

module.exports = BinarySearchTree

let b = new BinarySearchTree()
b.insert(9).insert(2).insert(5).insert(11).insert(10).insert(24).insert(17).insert(3).insert(1).insert(5).insert(0)
  .insert(1).insert(-1).insert(0).insert(-1).insert(3).insert(2).insert(2)

// b.preOrderTranversal(function(key) {
//   console.log(key);
// })

// console.log(b.search(1));
// console.log(b.remove(2));
// b.preOrderTranversal(function(key) {
//   console.log(key);
// })
// console.log(b.remove(17));
// b.preOrderTranversal(function(key) {
//   console.log(key);
// })
console.log(b.remove(9));
b.preOrderTranversal(function(key) {
  console.log(key);
})